| 翻訳と辞書 |
| Kőnig's theorem (graph theory) ： ウィキペディア英語版 |
Kőnig's theorem (graph theory)
In the mathematical area of graph theory, König's theorem, proved by , describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.
== Setting ==
A graph is bipartite if its vertices can be partitioned into two sets such that each edge has one endpoint in each set.〔, pp. 4–5.〕 A vertex cover in a graph is a set of vertices that includes at least one endpoint of every edge, and a vertex cover is ''minimum'' if no other vertex cover has fewer vertices.〔Called a ''covering'' and a ''minimum covering'' respectively by , p. 73.〕 A matching in a graph is a set of edges no two of which share an endpoint, and a matching is ''maximum'' if no other matching has more edges.〔, p. 70.〕 König's theorem states that, in any bipartite graph, the number of edges in a maximum matching is equal to the number of vertices in a minimum vertex cover.〔, Theorem 5.3, p. 74; .〕
For graphs that are not bipartite, the maximum matching and minimum vertex cover problems are very different in complexity: maximum matchings can be found in polynomial time for any graph, while minimum vertex cover is NP-complete. The complement of a vertex cover in any graph is an independent set, so a minimum vertex cover is complementary to a maximum independent set; finding maximum independent sets is another NP-complete problem. The equivalence between matching and covering articulated in König's theorem allows minimum vertex covers and maximum independent sets to be computed in polynomial time for bipartite graphs, despite the NP-completeness of these problems for more general graph families.〔, (Exercise 261, p. 342 ).〕
König's theorem is equivalent to numerous other min-max theorems in graph theory and combinatorics, such as Hall's marriage theorem and Dilworth's theorem. Since bipartite matching is a special case of maximum flow, the theorem also results from the max-flow min-cut theorem.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Kőnig's theorem (graph theory)」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|